{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Third Maximum Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: thirdMax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第三大的数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非空数组，返回此数组中 <strong>第三大的数</strong> 。如果不存在，则返回数组中最大的数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[3, 2, 1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第三大的数是 1 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1, 2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>第三大的数不存在, 所以返回最大的数 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[2, 2, 3, 1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。\n",
    "此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能设计一个时间复杂度 <code>O(n)</code> 的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [third-maximum-number](https://leetcode.cn/problems/third-maximum-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [third-maximum-number](https://leetcode.cn/problems/third-maximum-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1]', '[1,2]', '[2,2,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        a = nums[0]\n",
    "        flag=1\n",
    "        for i in nums[1::1]:\n",
    "            if a>i:\n",
    "                a=i\n",
    "                flag+=1\n",
    "            if flag==3:\n",
    "                return a\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                diff += 1\n",
    "                if diff == 3:\n",
    "                    return nums[i]\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        length=len(nums)-2\n",
    "        max=length+1\n",
    "        cnt=0\n",
    "\n",
    "        while length>=0:\n",
    "            if nums[length]==nums[length+1]:\n",
    "                pass\n",
    "            else:\n",
    "                cnt+=1\n",
    "            if cnt==2:\n",
    "                return nums[length]\n",
    "            length-=1\n",
    "        return nums[max]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums1=[]\n",
    "        for i in nums:\n",
    "            if i not in nums1:\n",
    "                nums1.append(i)\n",
    "            else:\n",
    "                continue\n",
    "        if len(nums1)<=2:\n",
    "            return max(nums1)\n",
    "        else:\n",
    "            #反转找到第三大\n",
    "            #nums1.sort(reverse=True)\n",
    "            #return nums1[2]\n",
    "            #移除元素得到第三大\n",
    "            nums1.remove(max(nums1))\n",
    "            nums1.remove(max(nums1))\n",
    "        return max(nums1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        biggest, second, third = float('-inf'), float('-inf'), float('-inf')\n",
    "        for num in nums:\n",
    "            if num > biggest:\n",
    "                biggest, second, third = num, biggest, second\n",
    "            elif biggest > num > second:\n",
    "                second, third = num, second\n",
    "            elif second > num > third:\n",
    "                third = num\n",
    "        return biggest if third == float('-inf') else third\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        dif = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]!= nums[i-1]:\n",
    "                dif +=1\n",
    "                if dif ==3:\n",
    "                    return nums[i]\n",
    "        return nums[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        count = 0\n",
    "        list1 = []\n",
    "        for i in nums:\n",
    "            if i not in list1:\n",
    "                list1.append(i)\n",
    "                count +=1\n",
    "            if count == 3:\n",
    "                return i\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums,reverse = True)\n",
    "        diff = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] != nums[i+1]:\n",
    "                diff += 1\n",
    "            if diff == 3:\n",
    "                return nums[i+1]\n",
    "        return nums[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = None, None, None\n",
    "        for num in nums:\n",
    "            if a is None or num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif a > num and (b is None or num > b):\n",
    "                b, c = num, b\n",
    "            elif b is not None and b > num and (c is None or num > c):\n",
    "                c = num\n",
    "        return a if c is None else c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        c=[]\n",
    "        for i in nums:\n",
    "            if i not in c:\n",
    "                c.append(i)\n",
    "        if len(c)<3:\n",
    "            return max(nums)\n",
    "        return c[2]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            if i not in ans:\n",
    "                ans.append(i)\n",
    "        if len(ans) < 3:\n",
    "            return(max(ans))\n",
    "        else:\n",
    "            for i in range(3):\n",
    "                for j in range(i+1,len(ans)):\n",
    "                    if ans[j] > ans[i]:\n",
    "                        temp = ans[i]\n",
    "                        ans[i] = ans[j]\n",
    "                        ans[j] = temp\n",
    "            return(ans[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def thirdMax(self, nums: List[int]) -> int:\n",
    "#         a=list(set(nums))\n",
    "#         a.sort()\n",
    "#         if len(a)<3:\n",
    "#             return a[-1]\n",
    "#         else:\n",
    "#             return a[-3]\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "\n",
    "        l  = len(nums)\n",
    "\n",
    "        ## 长度小于等于 2 时，取最大值即可\n",
    "        if l <= 2:\n",
    "            return max(nums[0], nums[l - 1])\n",
    "\n",
    "        first = second = third = float('-inf')\n",
    "\n",
    "        for cur in nums :\n",
    "\n",
    "            ## 由于第几大都是不能重复的，也就是说当前元素 cur 如果等于 first, second 时，忽略即可\n",
    "            if cur == first or cur == second :\n",
    "                ## 忽略当前元素\n",
    "                continue\n",
    "\n",
    "            ## 当前元素大于 first, 更新 first, second, third\n",
    "            if cur > first:\n",
    "                third = second\n",
    "                second = first\n",
    "                first = cur\n",
    "                continue\n",
    "\n",
    "            ## 当前元素大于 second, 更新 third, second 指针\n",
    "            if cur > second:\n",
    "                third = second\n",
    "                second = cur\n",
    "                continue\n",
    "\n",
    "            ## 大于 third 时，更新 third 指针\n",
    "            if cur > third :\n",
    "                third = cur\n",
    "\n",
    "\n",
    "        if third == float('-inf'):\n",
    "            return first\n",
    "        else :\n",
    "            return third"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = float('-inf'), float('-inf'), float('-inf')\n",
    "        for num in nums:\n",
    "            if num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif a > num > b:\n",
    "                b, c = num, b\n",
    "            elif b > num > c:\n",
    "                c = num\n",
    "        return a if c == float('-inf') else c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        count=0\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[n-i-1]>nums[n-i-2]:\n",
    "                count+=1\n",
    "            if count==2:\n",
    "                return nums[n-i-2]\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        # 1.先把nums倒序\n",
    "        nums.sort(reverse=True)\n",
    "        # 2.新建一个指针P，变量res和计数变量c\n",
    "        P = 0\n",
    "        res = inf\n",
    "        c = 0\n",
    "        # 3.从左开始遍历，每次出现不一样的数字就让c+1，直到c==3或者遍历完整个nums就停止循环\n",
    "        while c < 3 and P < len(nums):\n",
    "            if nums[P] < res:\n",
    "                res = nums[P]\n",
    "                c += 1\n",
    "            P += 1\n",
    "        if c == 3:\n",
    "            return res\n",
    "        else:\n",
    "            return nums[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        #记录第一大，第二大，第三大的数字\n",
    "        first,second,third= -2**31-1, -2**31-1, -2**31-1\n",
    "        for m in nums:\n",
    "            if m == first or m == second or m == third: #先判断相等的情况\n",
    "                continue\n",
    "            if m > first:\n",
    "                first,second,third = m,first,second\n",
    "            elif m > second:\n",
    "                second,third = m,second\n",
    "            elif m > third:\n",
    "                third = m \n",
    "        return first if third == -2**31-1 else third"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                diff += 1\n",
    "                if diff == 3:\n",
    "                    return nums[i]\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        first = second = third = float('-inf')\n",
    "\n",
    "        for num in nums:\n",
    "            if num > first:\n",
    "                first, second, third = num, first, second\n",
    "            elif first > num > second:\n",
    "                second, third = num, second\n",
    "            elif second > num > third:\n",
    "                third = num\n",
    "\n",
    "        # 如果第三大的数仍然是负无穷，则返回最大的数\n",
    "        return third if third != float('-inf') else first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        res = []\n",
    "        n = 0\n",
    "        for i in nums:\n",
    "            if not res:\n",
    "                res = [i]\n",
    "                n+=1\n",
    "            elif i==res[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                res.append(i)\n",
    "                n+=1\n",
    "                if n==3:\n",
    "                    return res[-1]\n",
    "        if n<=2:\n",
    "            return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        res = self.sort_func(nums)\n",
    "        if len(res)>=3:\n",
    "            return res[-3]\n",
    "        else:\n",
    "            return res[-1]\n",
    "\n",
    "    def sort_func(self,nums):\n",
    "        res =[]\n",
    "        for i in nums:\n",
    "            if i not in res:\n",
    "                if res:\n",
    "                    if i < res[0]:\n",
    "                        res.insert(0,i)\n",
    "                    else:\n",
    "                        for j in range(len(res)):\n",
    "                            if j+1 != len(res):\n",
    "                                if i >res[j] and i <res[j+1]:\n",
    "                                    res.insert(j+1,i)\n",
    "                                    break\n",
    "                            else:\n",
    "                                res.append(i)\n",
    "                else:\n",
    "                    res.append(i)\n",
    "        return res\n",
    "    #    return self.sort(nums)\n",
    "\n",
    "    # def sort(self,nums):\n",
    "    #     res = self.sort_func(self.sort_insert_mid(nums))\n",
    "    #     if len(res)>=3:\n",
    "    #         return res[-3]\n",
    "    #     else:\n",
    "    #         return res[-1]\n",
    "\n",
    "    # def sort_insert_mid(self,list):\n",
    "    #     for i in range(1, len(list)):\n",
    "    #         tmp = list[i]\n",
    "    #         low = 0\n",
    "    #         high = i - 1\n",
    "    #         while low <= high:\n",
    "    #             m = int((low + high) / 2)\n",
    "    #             if tmp > list[m]:\n",
    "    #                 low = m + 1\n",
    "    #             else:\n",
    "    #                 high = m - 1\n",
    "    #         j = i - 1\n",
    "    #         while j >= high + 1:\n",
    "    #             list[j + 1] = list[j]\n",
    "    #             j -= 1\n",
    "    #         list[high + 1] = tmp\n",
    "    #     return list      \n",
    "\n",
    "    # def sort_func(self,nums):\n",
    "    #     res = []\n",
    "    #     for i in nums:\n",
    "    #         if  i not in res:\n",
    "    #             res.append(i)\n",
    "    #     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                diff += 1\n",
    "                if diff == 3:  # 此时 nums[i] 就是第三大的数\n",
    "                    return nums[i]\n",
    "        return nums[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            res = []\n",
    "            for i in nums:\n",
    "                if i not in res:\n",
    "                    res.append(i)\n",
    "            res.sort(reverse=True)\n",
    "            try:\n",
    "                return res[2]\n",
    "            except:\n",
    "                return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i-1] != nums[i]:\n",
    "                diff += 1\n",
    "                if diff == 3:\n",
    "                    return nums[i]\n",
    "            \n",
    "        return nums[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        heap = []\n",
    "        for n in nums:\n",
    "            if n in heap:\n",
    "                continue \n",
    "\n",
    "            heappush(heap, n)\n",
    "            if len(heap) > 3:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        if len(heap) == 3:\n",
    "            return heapq.heappop(heap)\n",
    "        else:\n",
    "            return heap[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "       return self.sort(nums)\n",
    "\n",
    "    def sort(self,nums):\n",
    "        res = self.sort_func(self.sort_insert_mid(nums))\n",
    "        if len(res)>=3:\n",
    "            return res[-3]\n",
    "        else:\n",
    "            return res[-1]\n",
    "\n",
    "    def sort_insert_mid(self,list):\n",
    "        for i in range(1, len(list)):\n",
    "            tmp = list[i]\n",
    "            low = 0\n",
    "            high = i - 1\n",
    "            while low <= high:\n",
    "                m = int((low + high) / 2)\n",
    "                if tmp > list[m]:\n",
    "                    low = m + 1\n",
    "                else:\n",
    "                    high = m - 1\n",
    "            j = i - 1\n",
    "            while j >= high + 1:\n",
    "                list[j + 1] = list[j]\n",
    "                j -= 1\n",
    "            list[high + 1] = tmp\n",
    "        return list      \n",
    "\n",
    "    def sort_func(self,nums):\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            if  i not in res:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = None, None, None\n",
    "        for num in nums:\n",
    "            if a is None or num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif a > num and (b is None or num > b):\n",
    "                b, c = num, b\n",
    "            elif b is not None and b > num and (c is None or num > c):\n",
    "                c = num\n",
    "        return a if c is None else c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        ans = [float('-inf'), float('-inf'), float('-inf')]\n",
    "        for num in nums:\n",
    "            if num > ans[0]:\n",
    "                ans = [num, ans[0], ans[1]]\n",
    "            elif num > ans[1] and num < ans[0]:\n",
    "                ans = [ans[0], num, ans[1]]\n",
    "            elif num > ans[2] and num < ans[1]:\n",
    "                ans = [ans[0], ans[1], num]\n",
    "        return ans[0] if ans[2] == float('-inf') else ans[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=sorted(nums)\n",
    "        a=max(nums)\n",
    "        b=min(nums)\n",
    "        if n<3:\n",
    "            return m[n-1]\n",
    "        if m[0]==m[n-1]:\n",
    "            return m[0]\n",
    "        if m[0]!=m[n-1]:\n",
    "            c=m.index(a)\n",
    "            if m[c-1]==b:\n",
    "                return a\n",
    "            else:\n",
    "                m=m[:c:]\n",
    "                d=m.index(m[c-1])\n",
    "                m=m[:d:]\n",
    "                return m[d-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                diff += 1\n",
    "                if diff == 3:  # 此时 nums[i] 就是第三大的数\n",
    "                    return nums[i]\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        differ = 1\n",
    "        nums.sort(reverse = True)\n",
    "        for num in range(1, len(nums)):\n",
    "            if nums[num] != nums[num-1]:\n",
    "                differ += 1\n",
    "            if differ == 3:\n",
    "                return nums[num]\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = float('-inf'), float('-inf'), float('-inf')\n",
    "        for num in nums:\n",
    "            if num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif a > num > b:\n",
    "                a, b, c = a, num, b\n",
    "            elif b > num > c:\n",
    "                c = num\n",
    "        if c == float('-inf'):\n",
    "            return a\n",
    "        else:\n",
    "            return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = -float('inf'), -float('inf'), -float('inf')\n",
    "        for num in nums:\n",
    "            if num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif b < num < a:\n",
    "                b, c = num, b\n",
    "            elif c < num < b:\n",
    "                c = num\n",
    "        print(a, b, c)\n",
    "        return c if c != -float('inf') else a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        heap = []\n",
    "        for n in nums:\n",
    "            if n in heap:\n",
    "                continue \n",
    "\n",
    "            heappush(heap, n)\n",
    "            if len(heap) > 3:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        if len(heap) == 3:\n",
    "            return heapq.heappop(heap)\n",
    "        else:\n",
    "            return heap[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        fir, sec, thir = nums[0], nums[0], nums[0]\n",
    "        for i in nums:\n",
    "            if i > fir:\n",
    "                thir, sec, fir = sec, fir, i\n",
    "            elif fir > i and (i > sec or sec == fir):\n",
    "                sec, thir = i, sec\n",
    "            elif sec > i and (i > thir or thir == sec or thir == fir):\n",
    "                thir = i\n",
    "        if fir > sec > thir:\n",
    "            return thir\n",
    "        return fir"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "\n",
    "        ans = set()\n",
    "        while (len(ans) < 3) and (n > 0):\n",
    "            pivot_idx = 0\n",
    "\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                if nums[i] < nums[pivot_idx]:\n",
    "                    nums[pivot_idx], nums[i] = nums[i], nums[pivot_idx]\n",
    "\n",
    "                pivot_idx = i\n",
    "                i += 1\n",
    "\n",
    "            n -= 1\n",
    "            ans.add(nums[pivot_idx])\n",
    "            \n",
    "        return min(ans) if len(ans) == 3 else max(ans)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        s = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in s:\n",
    "                s.add(num)\n",
    "                if len(s) > 3:\n",
    "                    s.pop(0)\n",
    "        if len(s) == 3:\n",
    "            return s[0]\n",
    "        else:\n",
    "            return s[-1]\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "\n",
    "        ans = set()\n",
    "        while (len(ans) < 3) and (n > 0):\n",
    "            print(\"###############\")\n",
    "\n",
    "            pivot_idx = 0\n",
    "            max_idx = 0\n",
    "\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                print(i, nums[pivot_idx], nums[i])\n",
    "                \n",
    "                if nums[i] < nums[pivot_idx]:\n",
    "                    nums[pivot_idx], nums[i] = nums[i], nums[pivot_idx]\n",
    "                else:  \n",
    "                    max_idx = i \n",
    "                    \n",
    "                pivot_idx = i\n",
    "                i += 1\n",
    "\n",
    "            n -= 1\n",
    "            ans.add(nums[pivot_idx])\n",
    "            \n",
    "\n",
    "        if len(ans) == 3:\n",
    "            return min(ans)\n",
    "        else:\n",
    "            return max(ans)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "\n",
    "        ans = set()\n",
    "        while (len(ans) < 3) and (n > 0):\n",
    "            pivot_idx = 0\n",
    "\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                if nums[i] < nums[pivot_idx]:\n",
    "                    nums[pivot_idx], nums[i] = nums[i], nums[pivot_idx]\n",
    "\n",
    "                pivot_idx = i\n",
    "                i += 1\n",
    "\n",
    "            n -= 1\n",
    "            ans.add(nums[pivot_idx])\n",
    "            \n",
    "        if len(ans) == 3:\n",
    "            return min(ans)\n",
    "        else:\n",
    "            return max(ans)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        s=SortedList()\n",
    "        for i in nums:\n",
    "            if i not in s:          #将s中没有的数加入s\n",
    "                s.add(i)\n",
    "                if len(s)>3:          #s长度超过3，去掉最小的数\n",
    "                   s.pop(0)\n",
    "        if len(s)==3:    \n",
    "            return s[0]       #返回第三大的值\n",
    "        else:\n",
    "            return s[-1]                 #返回最大值\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        def merge(s1, s2):\n",
    "            f1 = 0\n",
    "            f2 = 0\n",
    "            ans = []\n",
    "            \n",
    "            while f1 < len(s1) and f2 < len(s2):\n",
    "                if s1[f1] <= s2[f2]:\n",
    "                    ans.append(s1[f1])\n",
    "                    f1 += 1\n",
    "                else:\n",
    "                    ans.append(s2[f2])\n",
    "                    f2 += 1\n",
    "            \n",
    "            if f2 < len(s2):\n",
    "                ans += s2[f2:]\n",
    "            \n",
    "            if f1 < len(s1):\n",
    "                ans += s1[f1:]\n",
    "            \n",
    "            return ans\n",
    "        def mergesort(nums):\n",
    "            if len(nums) <= 1:\n",
    "                return nums\n",
    "            \n",
    "            mid = len(nums) // 2\n",
    "            s1 = mergesort(nums[:mid])\n",
    "            s2 = mergesort(nums[mid:])\n",
    "            return merge(s1,s2)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        nums.sort()\n",
    "        count = 1\n",
    "        point = len(nums) - 1\n",
    "        while count <= 2:\n",
    "            if point < 0:\n",
    "                return nums[-1]\n",
    "            \n",
    "            if nums[point] == nums[point - 1]:\n",
    "                point = point - 1\n",
    "            else:\n",
    "                count = count + 1\n",
    "                point = point - 1\n",
    "\n",
    "        return nums[point]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        sortedlist = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in sortedlist:\n",
    "                sortedlist.add(num)\n",
    "                if len(sortedlist) > 3:\n",
    "                    sortedlist.pop(0)\n",
    "        \n",
    "        return sortedlist[0] if len(sortedlist) == 3 else sortedlist[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in s:\n",
    "                s.add(num)\n",
    "                if len(s) > 3:\n",
    "                    s.pop(0)\n",
    "        return s[0] if len(s) == 3 else s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in s:\n",
    "                s.add(num)\n",
    "                if len(s) > 3:\n",
    "                    s.pop(0)\n",
    "        return s[0] if len(s) == 3 else s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a, b, c = None, None, None\n",
    "        for num in nums:\n",
    "            if a is None or num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif a > num and (b is None or num > b):\n",
    "                b, c = num, b\n",
    "            elif b is not None and b > num and (c is None or num > c):\n",
    "                c = num\n",
    "        return a if c is None else c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers  import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        for x in nums:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s) > 3:\n",
    "                    s.pop(0)\n",
    "        return s[0] if len(s) == 3 else s[-1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        # if len(nums)<=3:\n",
    "\n",
    "        # else:\n",
    "        #     newnums=list(set(nums))\n",
    "        #     sorted(newnums)\n",
    "        #     if len(newnums):\n",
    "        #         del newnums[-2:]\n",
    "        # if len(newnums):\n",
    "        #      return newnums[-1]\n",
    "\n",
    "        s=SortedList()\n",
    "        for x in nums:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s)>3:\n",
    "                    s.pop(0)\n",
    "        return s[0] if len(s)==3 else s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        sortedlist = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in sortedlist:\n",
    "                sortedlist.add(num)\n",
    "                if len(sortedlist) > 3:\n",
    "                    sortedlist.pop(0)\n",
    "        \n",
    "        return sortedlist[0] if len(sortedlist) == 3 else sortedlist[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in res:\n",
    "                res.append(nums[i])\n",
    "        print(res)\n",
    "        if len(res) <= 2:\n",
    "            return res[0]\n",
    "        if len(res) >= 3:\n",
    "            return res[2]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        sortedlist = SortedList()\n",
    "        for num in nums:\n",
    "            if num not in sortedlist:\n",
    "                sortedlist.add(num)\n",
    "                if len(sortedlist) > 3:\n",
    "                    sortedlist.pop(0)\n",
    "        \n",
    "        return sortedlist[0] if len(sortedlist) == 3 else sortedlist[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        1.排序\n",
    "        2.如果第三大的数，那么就是进行输出,就是进行比较，设置最小的为第一个数字\n",
    "        3.如果不存在: 排序完只有两个数字，那么就返回最大的数字\n",
    "        1 2 2 2 3\n",
    "        \"\"\"\n",
    "        nums = sorted(nums)\n",
    "        print(nums)\n",
    "        x = nums[len(nums) - 1]\n",
    "        index = 1\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if x > nums[i]:\n",
    "                x = nums[i]\n",
    "                index = index + 1\n",
    "                if index == 3:\n",
    "                    return x\n",
    "        \n",
    "        if index < 3:\n",
    "            return nums[len(nums) - 1]\n",
    "            \n",
    "            \n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        my_set = set(nums)\n",
    "        if len(my_set) <3:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            max1 = max(my_set)\n",
    "            my_set.remove(max1)\n",
    "            max2 = max(my_set)\n",
    "            my_set.remove(max2)\n",
    "            return max(my_set)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        li = sorted(list(set(nums)), reverse=True)\n",
    "        return  li[2] if len(li)>=3 else li[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        diff = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                diff += 1\n",
    "                if diff == 3:\n",
    "                    return nums[i]\n",
    "        return nums[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        res=SortedList()\n",
    "        for num in nums:\n",
    "            if num not in res:\n",
    "                res.add(num)\n",
    "                if len(res)>3:\n",
    "                    res.pop(0)\n",
    "        return res[0] if len(res)==3 else res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        n = len(a)\n",
    "        for i in range(n):\n",
    "            if n<=2 :\n",
    "                return a[-1]\n",
    "            else:\n",
    "                return a[-3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        l = list(set(nums))\n",
    "        l.sort(reverse=True)\n",
    "        if len(l) >= 3:\n",
    "            return l[2]\n",
    "        return l[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums=set(nums)\n",
    "        if len(nums)<3:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            nums.remove(max(nums))\n",
    "            nums.remove(max(nums))\n",
    "            return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        if len(nums) < 3:\n",
    "            return nums[-1]\n",
    "        else:\n",
    "            return nums[-3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        count = collections.Counter(nums)\n",
    "        sub_nums = list(count.keys())\n",
    "        sub_nums.sort()\n",
    "\n",
    "        if len(sub_nums) < 3:\n",
    "            return max(sub_nums)\n",
    "        else:\n",
    "            return sub_nums[-3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        # 去重\n",
    "        ll = set(nums)\n",
    "        if len(ll) < 3:\n",
    "            return max(ll)\n",
    "        #\n",
    "        a = b = c = -2 ** 31\n",
    "        for n in ll:\n",
    "            if n > a:\n",
    "                c = b\n",
    "                b = a\n",
    "                a = n\n",
    "            elif n > b and n != a:\n",
    "                c = b\n",
    "                b = n\n",
    "            elif n > c and n != a and n != b:\n",
    "                c = n\n",
    "        #\n",
    "        return c\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        # 去重\n",
    "        ll = set(nums)\n",
    "        if len(ll) < 3:\n",
    "            return max(ll)\n",
    "        #\n",
    "        a = b = c = -2 ** 31\n",
    "        for n in ll:\n",
    "            if n > a:\n",
    "                c = b\n",
    "                b = a\n",
    "                a = n\n",
    "            elif n > b:\n",
    "                c = b\n",
    "                b = n\n",
    "            elif n > c:\n",
    "                c = n\n",
    "        #\n",
    "        return c\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort(reverse=True)\n",
    "        if len(nums)<3:\n",
    "            return nums[0]\n",
    "        return nums[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        l = list(set(nums))\n",
    "        l.sort()\n",
    "        if len(l) < 3:\n",
    "            return l[-1]\n",
    "        else:\n",
    "            return l[-3] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        #长度小于3的，直接返回最大值\n",
    "        ll_nums = list(set(nums))\n",
    "        if len(ll_nums) < 3:\n",
    "            return max(ll_nums)\n",
    "        #初始化最大值，次大值，第三大值\n",
    "        a = b = c = float('-inf')\n",
    "        #遍历列表：\n",
    "        for num in nums:\n",
    "            #大于最大值，依次更新，这里要注意更新顺序，先更新c, 然后b, 最后a\n",
    "            if num > a:\n",
    "                c = b\n",
    "                b = a\n",
    "                a = num\n",
    "            #更新次大值\n",
    "            elif num > b and num != a:\n",
    "                c = b\n",
    "                b = num\n",
    "            #更新第三大值\n",
    "            elif num > c and num != a and num != b:\n",
    "                c = num\n",
    "        return c\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        new_num = list(set(nums))\n",
    "        new_num.sort(reverse = True)\n",
    "        if len(new_num) >= 3:\n",
    "            return new_num[2]\n",
    "        else:\n",
    "            return new_num[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums_set = list(set(nums))\n",
    "        nums_set.sort()\n",
    "        if len(nums_set) < 3:\n",
    "            return nums_set[-1]\n",
    "        else:\n",
    "            return nums_set[-3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        negNums = [-x for x in nums]\n",
    "        heapq.heapify(negNums)\n",
    "\n",
    "        count = 0\n",
    "        currMax = -sys.maxsize\n",
    "        allMax = -sys.maxsize\n",
    "        while negNums and count != 3:\n",
    "            num = heapq.heappop(negNums)\n",
    "            if allMax == -sys.maxsize:\n",
    "                allMax = num\n",
    "            \n",
    "            if currMax != num:\n",
    "                currMax = num\n",
    "                count += 1\n",
    "        \n",
    "        return -currMax if count == 3 else -allMax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = sorted(list(set(nums)), reverse = True)\n",
    "        return nums[2] if len(nums) > 2 else nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        # 第三大的数字\n",
    "        # n = list(set(nums))\n",
    "        # n1 = sorted(n)[::-1]\n",
    "        # print(n1)\n",
    "        # if len(n1) < 3:\n",
    "        #     return max(n1)\n",
    "        \n",
    "\n",
    "        # print(n1[2])\n",
    "        # return n1[2]\n",
    "\n",
    "        # 直接渠取倒的数值\n",
    "\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "\n",
    "        if len(a) < 3:\n",
    "            return a[-1]\n",
    "        return a[-3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort(reverse=True)\n",
    "        if len(nums) >= 3:\n",
    "            return nums[2]\n",
    "        else:\n",
    "            return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "K = 3\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        for num in set(nums):\n",
    "            heapq.heappush(pq, num)\n",
    "            if len(pq) > K:\n",
    "                heapq.heappop(pq)\n",
    "        return heapq.heappop(pq) if len(pq) == K else pq[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort(reverse=True)\n",
    "        try:\n",
    "            return nums[2]\n",
    "        except:\n",
    "            return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        d1 = None\n",
    "        d2 = None\n",
    "        d3 = None\n",
    "        for i in nums:\n",
    "            if d1 is None:\n",
    "                d1 = i\n",
    "            elif i >= d1:\n",
    "                d3=d2\n",
    "                d2=d1\n",
    "                d1=i\n",
    "            elif d2 is None:\n",
    "                d2 = i\n",
    "            elif i >=d2:\n",
    "                d3=d2\n",
    "                d2=i\n",
    "            elif d3 is None:\n",
    "                d3 = i\n",
    "            elif i>=d3:\n",
    "                d3 = i\n",
    "        if d3 is None:\n",
    "            return d1\n",
    "        else:\n",
    "            return d3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: list[int]) -> int:\n",
    "        ls=sorted(list(set(nums)),reverse=True)\n",
    "        if len(ls)>=3:\n",
    "            return ls[2]\n",
    "        else:\n",
    "            return max(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        a=list(set(nums))\n",
    "        a.sort()\n",
    "        if len(a)<3:\n",
    "            return a[-1]\n",
    "        else:\n",
    "            return a[-3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        if 0<len(nums)<3:\n",
    "            return (max(nums))\n",
    "        elif len(nums)==0:\n",
    "            return (nums)\n",
    "        else:\n",
    "            a=list(set(nums))\n",
    "            a.sort(reverse=True)\n",
    "            if len(a)<3:\n",
    "                return (max(a))\n",
    "            else:\n",
    "                return (a[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        arr = sorted(set(nums), reverse=True)\n",
    "        return arr[0] if len(arr) < 3 else arr[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        new_li = list(set(nums))\n",
    "        new_li.sort(reverse=True)\n",
    "        if len(new_li) >= 3:\n",
    "            return new_li[2]\n",
    "        else:\n",
    "            return new_li[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        new_num = list(set(nums))\n",
    "        new_num.sort()\n",
    "        if len(new_num) >= 3:\n",
    "            return new_num[::-1][2]\n",
    "        else:\n",
    "            return new_num[::-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def thirdMax(self, nums: List[int]) -> int:\n",
    "        nums1=set(nums)\n",
    "        \n",
    "        if len(nums1)<3:\n",
    "            return max(nums1)\n",
    "        else:\n",
    "            list1=sorted(nums1)\n",
    "            return list1[-3]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
